import java.util.ArrayList;
import java.util.List;

public class StringSearch
{
    public static void main(String[] args)
    {
        StringSearch.printArrayList(boyerMoore("bdd","bbddddd"));
    }

    /**
     * Find all instances of pattern in text using Boyer-Moore algorithm.
     * Use buildBoyerMooreCharTable to build your reference table.
     *
     * @param pattern
     * The String to find
     * @param text
     * The String to look through
     * @return
     * A List of starting indices where pattern was found in text
     */
    public static List<Integer> boyerMoore(String pattern, String text)
    {
        List<Integer> indices = new ArrayList<Integer>();
        int[] indexTable =  StringSearch.buildBoyerMooreCharTable(pattern);
        int patternPointer = pattern.length()-1;
        int textPointer =  pattern.length()-1;

        boolean keepGoing;

        //as long as you haven't gone beyond the text
        while(textPointer < text.length())
        {
            keepGoing = true;
            int initialTextPointer = textPointer;
            while(keepGoing)
            {
                char t = text.charAt(textPointer);
                char c = pattern.charAt(patternPointer);

                if(c != t)
                {
                    int shift = patternPointer - (pattern.length()-1) + indexTable[(int)t];
                    textPointer = (shift > 0) ? initialTextPointer + shift : initialTextPointer + 1 ;
                    patternPointer = pattern.length()-1;
                    keepGoing = false;
                }
                else
                {
                    patternPointer --;
                    textPointer --;
                }
                if(patternPointer == -1)
                {
                    indices.add(++textPointer);
                    textPointer = initialTextPointer+1;
                    patternPointer = pattern.length()-1;
                    keepGoing = false;
                }
            }
        }
        return indices;
    }

    /**
     * Creates a table of distances from each character to the end.
     * Has an entry for every character from 0 to Character.MAX_VALUE.
     * For use with Boyer-Moore.
     *
     * If the character is in the string:
     * 		map[c] = length - last index of c - 1
     * Otherwise:
     * 		map[c] = length
     *
     * @param pattern
     * The string being searched for
     * @return
     * An int array for Boyer-Moore
     */
    public static int[] buildBoyerMooreCharTable(String pattern)
    {
        //map contains every possible character
        int[] map = new int[Character.MAX_VALUE + 1];
        //set the initial values in the table to the length of the pattern.
        for(int i = 0; i < map.length; i++)
        {
            map[i] = pattern.length();
        }
        //overwrite values of the letters in pattern with their last index in pattern.
        for(int i = 0; i < pattern.length(); i++)
        {
            int index = (int)pattern.charAt(i);
            map[index] = Math.max(1, pattern.length()-1-i);
        }
        return map;
    }

    /**
     * Find all instances of pattern in text using Knuth-Morris-Pratt algorithm.
     * Use buildKmpSuffixTable to build your reference table.
     *
     * @param pattern
     * The String to find
     * @param text
     * The String to look through
     * @return
     * A List of starting indices where pattern was found in text
     */
    public static List<Integer> kmp(String pattern, String text) {

        List<Integer> indices = new ArrayList<Integer>();
        int[] suffixTable =  StringSearch.buildKmpSuffixTable(pattern);
        int patternPointer = 0;
        int textPointer =  0;
        int initialTextPointer = 0;
        boolean added = true;

        //while you havent checked through the entire text.
        while(textPointer<text.length())
        {
            //reset the initialTextPointer after you reset the pattern pointer
            if(patternPointer == 0)
            {
                initialTextPointer = textPointer;
            }

            //keep going while the strings match.
            while(pattern.charAt(patternPointer) == text.charAt(textPointer))
            {
                patternPointer++;
                textPointer++;

                if(patternPointer > pattern.length()-1)
                {
                    System.out.println("ADD "+ initialTextPointer);
                    System.out.println();
                    indices.add(initialTextPointer);
                    added = true;
                }
                if(textPointer > text.length()-1)
                {
                    return indices;
                }
                if(patternPointer > pattern.length()-1)
                {
                    break;
                }


            }

            if(!added)
            {
                //found a problem before reaching the end of the suffix
                if(suffixTable[patternPointer] == -1)
                {
                    patternPointer = 0;
                    textPointer++;
                    if(textPointer == text.length()-1)
                    {
                        return indices;
                    }
                }
                else
                {
                    initialTextPointer += suffixTable[patternPointer];
                    patternPointer = suffixTable[patternPointer] ;
                }
            }
            else
            {
                textPointer = initialTextPointer +1;
                patternPointer = 0;
                added = false;
            }

        }
        return indices;
    }

    /**
     * Creates a table of matching suffix and prefix sizes.
     * For use with Knuth-Morris-Pratt.
     *
     * If i = 0:
     * 		map[i] = -1
     * If i > 0:
     * 		map[i] = size of largest common prefix and suffix for substring of size i
     *
     * @param pattern
     * The string bing searched for
     * @return
     * An int array for Knuth-Morris-Pratt
     */
    public static int[] buildKmpSuffixTable(String pattern)
    {
        int[] map = new int[pattern.length()];
        int count = 0;

        //for each position in the string, compare the prefix and suffix
        for (int i = 0; i < pattern.length()-1; i++)
        {
            //index 0 is always -1
            if(i == 0)
            {
                map[i] = -1;
            }
            else
            {
                //if the current sub pattern is broken, set count to the length of the subpattern at the place that was broken
                while (count > 0 && pattern.charAt(count) != pattern.charAt(i))
                {
                    count = map[count - 1];
                }
                if(count == -1)
                {
                    count = 0;
                }
                //increment the langth of the subpattern
                if (pattern.charAt(count) == pattern.charAt(i))
                {
                    count++;
                }
                map[i+1] = count;
            }
        }
        return map;
    }

    // This is the base to be used for Rabin-Karp. No touchy.
    private static final int BASE = 997;

    /**
     * Find all instances of pattern in text using Rabin-Karp algorithm.
     * Use hashString and updateHash to handle hashing.
     *
     * @param pattern
     * The String to find
     * @param text
     * The String to look through
     * @return
     * A List of starting indices where pattern was found in text
     */
    public static List<Integer> rabinKarp(String pattern, String text)
    {
        List<Integer> indices = new ArrayList<Integer>();
        if(pattern.length()>text.length())
        {
            return indices;
        }
        int patternHash = StringSearch.hashString(pattern);
        int textHash = StringSearch.hashString( text.substring(0,pattern.length()));
        int i = 0;
        while(i <= (text.length()-pattern.length()))
        {
            if(textHash == patternHash)
            {
                int textPointer = i;
                int patternPointer = 0;

                while(text.charAt(textPointer) == pattern.charAt(patternPointer))
                {
                    if(patternPointer == pattern.length()-1)
                    {
                        indices.add(i);
                        break;
                    }
                    textPointer++;
                    patternPointer++;
                }
            }
            if(text.length() > i+pattern.length())
            {
                textHash = StringSearch.updateHash(textHash, text.charAt(i+pattern.length()), text.charAt(i),pattern.length());
            }
            i++;
        }

        return indices;
    }

    /**
     * Hashes a string in a specified way.
     * For use with Rabin-Karp.
     *
     * This hash function will use BASE and the indices of the characters.
     * Each character at i is multiplied by BASE raised to the power of length - 1 - i
     * These values are summed to determine the entire hash.
     *
     * For example:
     * Hashing "bunn" as a substring of "bunny" with base 433
     * hash = b * 433 ^ 3 + u * 433 ^ 2 + n * 433 ^ 1 + n * 433 ^ 0
     *      = 98 * 433 ^ 3 + 117 * 433 ^ 2 + 110 * 433 ^ 1 + 110 * 433 ^ 0
     *      = 7977892179
     *
     * @param pattern
     * The String to be hashed
     * @return
     * A hash value for the string
     */
    public static int hashString(String pattern)
    {
        int lengthFromEnd = pattern.length()-1;
        int hash = 0;

        for(int i = 0; i < pattern.length(); i++)
        {
            int j = (int)pattern.charAt(i);

            hash += (j * StringSearch.myPow(BASE, lengthFromEnd));
            lengthFromEnd--;
        }
        return hash;
    }

    /**
     * Updates the oldHash in a specified way.
     * Follows the same hash formula as hashString.
     * For use with Rabin-Karp.
     *
     * To update the hash, remove the oldChar times BASE raised to the length - 1,
     * 		multiply by BASE, and add the newChar.
     * For example:
     * Shifting from "bunn" to "unny" in "bunny" with base 433
     * hash("unny") = (hash("bunn") - b * 433 ^ 3) * 433 + y * 433 ^ 0
     *              = (7977892179 - 98 * 433 ^ 3) * 433 + 121 * 433 ^ 0
     *              = 9519051770
     *
     * @param oldHash
     * The old hash to be updated
     * @param newChar
     * The new character added at the end of the substring
     * @param oldChar
     * The old character being removed from the front of the substring
     * @param length
     * The length of the hashed substring
     */
    public static int updateHash(int oldHash, char newChar, char oldChar, int length)
    {
        int remove = oldChar * StringSearch.myPow(BASE, length-1);
        return (oldHash - remove)*BASE + newChar;
    }

    /**
     * Prits an array list
     * @param list
     */
    private static void printArrayList(List<Integer> list)
    {
        for(int i : list)
        {
            System.out.println(i);
        }
    }

    /**
     * custom power function
     * @param base
     * @param exponent
     * @return
     */
    private static int myPow(int base, int exponent)
    {
        int tot = 1;
        for(int i = 0; i < exponent; i++)
        {
            tot*=base;
        }
        return tot;
    }

}
